﻿package zf.data.ds
{
	import zf.data.ds.node.DListNode;

	/**
	 * 双向数据链表，包括头和尾指针 
	 * @author Mike.zhang
	 * @langversion 3.0 
	 * @playerversion Flash 9 
	 * 
	 * @see zf.data.ds.node.DListNode
	 */
	public class DLinkedList implements ILinkedList
	{
		private var _head:DListNode;
		private var _tail:DListNode;
		private var _length:uint;

		/**
		 * 双向数据链表 
		 * @param args 链表数据
		 * 
		 */
		public function DLinkedList (... args)
		{
			head=tail=null;
			_length=0;
			if (args.length > 0)
			{
				append.apply (this,args);
			}
		}
		/**
		 * 头指针，指向第一个节点 
		 * @return 节点
		 * 
		 */
		public function get head ():DListNode
		{
			return _head;
		}

		public function set head (v:DListNode):void
		{
			_head=v;
		}

		/**
		 * 尾指针，指向最后一个节点 
		 * @return 节点
		 * 
		 */
		public function get tail ():DListNode
		{
			return _tail;
		}

		public function set tail (v:DListNode):void
		{
			_tail=v;
		}

		/**
		 * 链表长度，总计的节点个数 
		 * @return 链表长度
		 * 
		 */
		public function get length ():uint
		{
			return _length;
		}
		/**
		 * @inheritDoc
		 * 
		 */
		public function isEmpty ():Boolean
		{
			return length == 0;
		}
		/**
		 * @inheritDoc
		 * 
		 */
		public function toArray ():Array
		{
			var node:DListNode=head;
			var arr:Array=new Array  ;
			while (node)
			{
				arr.push (node.data);
				node=node.next;
			}
			return arr;
		}
		/**
		 * @inheritDoc
		 * 
		 */
		public function clear ():void
		{
			var node:DListNode=head;

			var tnode:DListNode;
			while (node)
			{
				tnode=node.next;
				node.prev=node.next=null;
				node=tnode;
			}
			head=tail=null;
			_length=0;
		}
		/**
		 * @inheritDoc
		 * 
		 */
		public function contains (obj:*):Boolean
		{
			var node:DListNode=head;
			while (node)
			{
				if (node.data == obj)
				{
					return true;
				}
				node=node.next;
			}
			return false;
		}

		/**
		 * 删除指针指向的节点 
		 * @param p 指针，指向要删除的节点
		 * @return 删除成功返回true
		 * 
		 */
		public function remove (p:DListPointer):Boolean
		{
			if (p.list != this || ! p.node)
			{
				return false;
			}
			var s:DListNode;
			var node:DListNode=p.node;
			if (p.node == head)
			{
				head=head.next;
			}
			else if (p.node == tail)
			{
				tail=tail.prev;
			}
			if (p.node)
			{
				p.node=p.node.next;
			}
			if (node.prev)
			{
				node.prev.next=node.next;
			}
			if (node.next)
			{
				node.next.prev=node.prev;
			}
			node.next=node.prev=null;

			if (head == null)
			{
				tail=null;
			}
			_length--;
			return true;
		}
		/**
		 * 添加一个或多个数据到链表尾，返回添加的第一个链表节点 
		 * @param args 要添加的一个或多个数据
		 * @return 添加到链表的第一个数据构成的节点
		 * 
		 */
		public function append (... args):DListNode
		{
			var l:uint=args.length;
			var node:DListNode=new DListNode(args[0]);
			if (head)
			{
				tail.insertAfter (node);
				tail=node;
			}
			else
			{
				head=tail=node;
			}
			if (l > 1)
			{
				var t:DListNode=node;
				for (var i:uint=1; i < l; i++)
				{
					node=new DListNode(args[i]);
					tail.insertAfter (node);
					tail=node;
				}
				_length+= l;
				return t;
			}
			_length++;
			return node;
		}
		/**
		 * 添加一个或多个数据到链表头，返回添加的第一个链表节点 
		 * @param args 要添加的一个或多个数据
		 * @return 添加到链表的第一个数据构成的节点
		 * 
		 */
		public function prepend (... args):DListNode
		{
			var l:uint=args.length;
			var node:DListNode=new DListNode(args[l - 1]);
			if (head)
			{
				head.insertBefore (node);
				head=head.prev;
			}
			else
			{
				head=tail=node;
			}
			if (l > 1)
			{
				var t:DListNode=node;
				for (var i:int=l - 2; i >= 0; i--)
				{
					node=new DListNode(args[i]);
					head.insertBefore (node);
					head=head.prev;
				}
				_length+= l;
				return t;
			}
			_length++;
			return node;
		}
		/**
		 * 连接一个或多个DLinkedList链表，并返回连接成的新链表，本链表保持不变 
		 * @param args 要连接的一个或多个DLinkedList链表
		 * @return 返回一个新的DLinkedList链表
		 * 
		 */
		public function concat (... args):DLinkedList
		{
			var c:DLinkedList=new DLinkedList  ;
			var a:DLinkedList;
			var n:DListNode;

			n=head;
			while (n)
			{
				c.append (n.data);
				n=n.next;
			}
			var k:uint=args.length;
			for (var i:uint=0; i < k; i++)
			{
				a=args[i];
				n=a.head;
				while (n)
				{
					c.append (n.data);
					n=n.next;
				}
			}
			return c;
		}
		/**
		 * 克隆链表 
		 * @return 链表 
		 * 
		 */
		public function clone ():DLinkedList
		{
			if (head)
			{
				var node:DListNode=head;
				var dll:DLinkedList=new DLinkedList  ;
				while (node)
				{
					dll.append (node.data);
					node=node.next;
				}
				return dll;
			}
			return null;
		}
		/**
		 * 创建一个指针，该指针初始指向链表头节点 
		 * @return 指针 DListPointer
		 * 
		 */
		public function creatPointer ():DListPointer
		{
			return new DListPointer(this,head);
		}
		/**
		 * 在链表中dlp所指向的节点后面插入一个数据为obj的节点,如果指针节点不存在，则直接插在链表尾
		 * @param dlp 指针，指向链表的节点
		 * @param obj 数据，要生成节点的数据
		 * @return 插入后形成的节点
		 * 
		 */
		public function insertAfter (dlp:DListPointer,obj:*):DListNode
		{
			if (dlp.list != this)
			{
				return null;
			}
			if (dlp.node)
			{
				var node:DListNode=new DListNode(obj);
				dlp.node.insertAfter (node);
				if (dlp.node == tail)
				{
					tail=node;
				}
				_length++;
				return node;
			}
			else
			{
				return append(obj);
			}
		}
		/**
		 * 在链表中dlp所指向的节点前面插入一个数据为obj的节点,如果指针节点不存在，则直接插在链表尾 
		 * @param dlp 指针，指向链表的节点
		 * @param obj 数据，要生成节点的数据
		 * @return 插入后形成的节点
		 * 
		 */
		public function insertBefore (dlp:DListPointer,obj:*):DListNode
		{
			if (dlp.list != this)
			{
				return null;
			}
			if (dlp.node)
			{
				var node:DListNode=new DListNode(obj);
				dlp.node.insertBefore (node);
				if (dlp.node == head)
				{
					head=node;
				}
				_length++;
				return node;
			}
			else
			{
				return prepend(obj);
			}
		}
		/**
		 * 使用全等（===），从form指针指向的节点开始向后查找，查找数据为obj的节点，并返回指向obj数据节点的指针。
		 * @param obj 待查找的数据
		 * @param form 查找开始的指针
		 * @return 如果有，返回指向该数据所在节点的指针，否则返回null
		 * 
		 */
		public function nodeOf (obj:*,form:DListPointer=null):DListPointer
		{
			if (form != null)
			{
				if (form.list != this)
				{
					return null;
				}
			}
			var node:DListNode=form == null?head:form.node;
			while (node)
			{
				if (node.data === obj)
				{
					return new DListPointer(this,node);
				}
				node=node.next;
			}
			return null;
		}
		/**
		 * 使用全等（===），从form指针指向的节点开始向前查找，查找数据为obj的节点，并返回指向obj数据节点的指针。
		 * @param obj 待查找的数据
		 * @param form 查找开始的指针
		 * @return 如果有，返回指向该数据所在节点的指针，否则返回null
		 * 
		 */
		public function lastNodeOf (obj:*,form:DListPointer=null):DListPointer
		{
			if (form != null)
			{
				if (form.list != this)
				{
					return null;
				}
			}
			var node:DListNode=form == null?tail:form.node;
			while (node)
			{
				if (node.data == obj)
				{
					return new DListPointer(this,node);
				}
				node=node.prev;
			}
			return null;
		}
		/**
		 * 删除链表中第一个节点，并返回该节点数据 
		 * @return 数据
		 * 
		 */
		public function removeHead ():*
		{
			if (head)
			{
				var obj:*=head.data;
				head=head.next;
				if (head)
				{
					head.prev=null;
				}
				else
				{
					tail=null;
				}
				_length--;
				return obj;
			}
			return null;
		}
		/**
		 * 删除链表中最后一个节点，并返回该节点数据 
		 * @return 数据
		 * 
		 */
		public function removeTail ():*
		{
			if (tail)
			{
				var obj:*=tail.data;
				tail=tail.prev;
				if (tail)
				{
					tail.next=null;
				}
				else
				{
					head=null;
				}
				_length--;
				return obj;
			}
			return null;
		}
		/**
		 * 倒转链表操作 
		 * 
		 */
		public function reverse ():void
		{
			if (_length < 2)
			{
				return;
			}
			var s:DListNode;
			var e:DListNode;
			var node:DListNode=head;
			head=tail;
			tail=node;
			while (node)
			{
				/*s=node.prev;
				e=node.next;
				node.prev=e
				node.next=s;
				node=e;*/
				e=node.next;
				node.next=node.prev;
				node.prev=e;
				node=e;
			}
		}
		/**
		 * 添加或删除链表中的数据，返回一个被删除的节点组成的链表，同时start指针将指向返回的链表的头 
		 * @param start 起始指针
		 * @param deleteCount 要操作的节点个数
		 * @param args 数据
		 * @return 被删除节点组成的链表
		 * 
		 */
		public function splice (start:DListPointer=null,deleteCount:int=int.MAX_VALUE,... args):DLinkedList
		{
			if (start)
			{
				if (start.list != this)
				{
					return null;
				}
			}
			else
			{
				start=creatPointer();
			}
			var node:DListNode=start.node;
			var pn:DListNode;
			var s:DListNode;
			var e:DListNode;
			var dll:DLinkedList=new DLinkedList  ;

			var i:int;
			if (deleteCount > 0)
			{
				s=node?node.prev:null;
				for (i=0; i < deleteCount && node; i++)
				{
					dll.append (node.data);
					pn=node;
					node=node.next;
					pn.prev=pn.next=null;
				}
				e=node;
				_length-= i;
			}
			else
			{
				e=node?node.next:null;
				for (i=0; i > deleteCount && node; i--)
				{
					dll.prepend (node.data);
					pn=node;
					node=node.prev;
					pn.prev=pn.next=null;
				}
				s=node;
				_length+= i;
			}
			var l:uint=args.length;
			var ts:DListNode;
			var te:DListNode;
			if (l > 0)
			{
				ts=new DListNode(args[0]);
				node=ts;
				for (i=1; i < l; i++)
				{
					node.insertAfter (new DListNode(args[i]));
					node=node.next;
				}
				te=node;
				if (_length == 0)
				{
					head=ts;
					tail=te;
					_length=l;
				}
				else
				{
					if (! s)
					{
						head=ts;
						te.next=e;
						e.prev=te;
					}
					else if (! e)
					{
						tail=te;
						ts.prev=s;
						s.next=ts;
					}
					else
					{
						s.next=ts;
						ts.prev=s;
						e.prev=te;
						te.next=e;
					}
					_length+= l;

				}
				start.list=dll;
				start.node=dll.head;
				return dll;
			}
			else
			{
				if (! s)
				{
					head=e;
				}
				else if (! e)
				{
					tail=s;
				}
				else
				{
					s.next=e;
					e.prev=s;
				}
				start.list=dll;
				start.node=dll.head;
				return dll;
			}
			return null;
		}
		/**
		 * 返回链表的描述信息 
		 * @return 格式[数据1,数据2, ...]
		 * 
		 */
		public function toString ():String
		{
			if (isEmpty())
			{
				return null;
			}
			var node:DListNode=head;
			//var str:String="[(Length:"+_length+" head:"+head+" tail:"+tail+") ";
			var str:String="[";
			while (node)
			{
				str+= node.toString() + ",";
				node=node.next;
			}
			str=str.slice(0,str.length - 1);
			str+= "]";
			return str;
		}
	}
}